1. Field of the Invention
The present invention relates to the field of graphic display systems. In particular, the present invention provides a method for minimizing the scan conversion time in generating a raster image on raster output devices.
2. Background of Prior Art
Scan conversion is a process of converting an image into a bitmap description suitable for display on a graphic display system. An image is represented by collections of points, lines, curves, and surfaces and stored in a refresh buffer. Each time some or all of the displayed image changes, scan conversion must be executed to update the resulting bitmap in the refresh buffer. See, J. D. Foley and A. Van Dam, Fundamentals of Interactive Computer Graphics, Addison-Wesley: 1984, pg 133. In general, the scan conversion process has the following steps: (1) approximate a curve by using either recursive subdivision or forward differencing, (2) determine where the approximated points fall on the resulting bitmap by using well known techniques such as the Bresenham algorithms, and (3) turn the pixels in the resulting bitmap on and off according the locations determined in step (2).
Recursive subdivision is an iterative process of breaking a curve into two smaller curves of the same type while still preserving the original shape of the curve. By this process, the arbitrary curve, for example second order Bezier Curves, is divided into two adjoining curves. The process of subdividing the midpoints is repeated on each of the two new curves. Eventually, this iterative process produces a series of points which approximates the arbitrary curve. See Bartels, R.; Beatty, J.; and Barsky, B., An Introduction To Splines For Use in Computer Graphics & Geometric Modeling, (Morgan Kaufmann Publishers, Inc.: 1987) p. 216-236. It should be understood that recursive subdivision is also known as refinement. Furthermore, recursive subdivision may be generalized from midpoint subdivision to arbitrary subdivision. For ease of comprehension, recursive subdivision is illustrated in this application by midpoint subdivision only.
Forward differencing is an incremental method of calculating the coordinates of an arbitrary curve for successive values of its parameter. Many curves and surfaces are formulated as parametric polynomial functions. The task of calculating points on a curve can be reduced to evaluating a polynomial. Under forward differencing, a parametric polynomial function is evaluated at equal intervals of its parameter. For example, in a quadratic polynomial, one adds the first partial differentials to the x and y coordinate of an end point of an arbitrary curve. This becomes the starting point for the next interval of parameters. The first partial differentials of the previous sum is added to the second partial differentials to derive the first partial differentials for the next interval of the parameters. This process is repeated until all the intervals of the parameters are accounted for. Graphically, forward differencing produces a succession of adjoining straight lines at different slopes which approximates the arbitrary curve. See Newman, W., and Sproul R., Principles of Interactive Computer Graphics, 2nd ed., (McGraw-Hill: 1979), p. 327-329.
Curves described by outline rendering techniques such as Bezier curves and B-Splines lend themselves naturally to manipulation by recursive subdivision and forward differencing. Outline rendering techniques are compact representations of images resulting from the use of splines to record and to generate the shape of curves. Splines are curves that are controlled by a small set of given control points and tangents. See Bartels, R.; Beatty, J.; and Barsky, B., An Introduction To Splines For Use in Computer Graphics & Geometric Modeling, (Morgan Kaufmann Publishers, Inc.: 1987), Chpt 9 and 10.
Bresenham algorithms are well known algorithms for generating lines, curves, and circles on a graphic display system. They are invoked hundreds or even thousands of times each time an image is created or modified. See Foley, J., and Van Dam, A., Fundamentals of Interactive Computer Graphics, (Addision-Wesley: 1984), Chpt. 11.
Although scan conversion serves a critical function in graphic display technology, it is a major bottleneck in updating the image display. It is therefore an object of the present invention to minimize the overhead presented by the scan conversion process. It is another object of the present invention to maximize the overall system performance of graphic display system by reducing the number of steps in executing the scan conversion process.